package com.tgy.algorithm.base;

import java.util.Arrays;

public class _快速排序_03 {

    public static int[] partition(int[] nums,int left,int right) {

        int[] res = new int[2];
        int povit = nums[right];
        int preIndex = left - 1;
        int index = left;
        int postIndex = right - 1;
        while (index <= postIndex) {
            int num = nums[index];
            if (num < povit) {
                if (preIndex + 1 != index) {
                    swap(nums, preIndex + 1, index);
                }
                preIndex++;
                index++;
            }else if(num > povit) {
                swap(nums, index, postIndex);
                postIndex--;
            }else {
                index++;
            }
        }

        // index > postIndex
        swap(nums, postIndex + 1, right);
        // 这里返回equal等于target在数组中两端的index
        res[0] = preIndex + 1;
        res[1] = postIndex + 1;
        return res;
    }

    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void quickSort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }

        doQuickSort(nums, 0, nums.length - 1);
    }

    public static void doQuickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }

        int[] partition = partition(nums, left, right);
        doQuickSort(nums, left, partition[0] - 1);
        doQuickSort(nums, partition[1] + 1, right);
    }

    public static void main(String[] args) {

        // 2 1 2 3 4 3 2
        // 1 | 2 2 >3 4 3< 2
        // 1 2 2 >3 1< 3 2
        // 1 |2 2 >1< 3 3 2
        // 1 1 | 2  2< >3 3 2
        // 1 2 2< 4 >3 3 2
        // 1 2 2< 2 >3 3 4
        int[] nums = new int[]{2, 1, 2, 3, 2, 3, 0};
        // 2, 1, 2, 3, 2, 3, 10
        // 2, 1, 2, 3, 2, 3, 10
//        int[] partition = partition(nums, 0, nums.length - 1);
//        System.out.println(Arrays.toString(partition));
        quickSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
